package leetcode.code0010;

public class Solution extends Solution10 {

	@Override
	public boolean isMatch(String s, String p) {
		char[] chars1 = s.toCharArray();
		char[] chars2 = p.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		boolean[][] dp = new boolean[len1 + 1][len2 + 1];
		dp[0][0] = true;// s,p都出0个字符,相等
		for (int i = 1; i <= len1; i++) {
			dp[i][0] = false;// p一个不出,不相等
		}
		for (int i = 1; i <= len2; i++) {
			dp[0][i] = false;// s一个不出,不相等
		}
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				// 以i,j位置结尾时dp[i][j]是否能匹配
				if (chars1[i - 1] == chars2[j - 1] || chars2[j - 1] == '.') {// 当前字符相等时
					if (dp[i - 1][j - 1]) {
						dp[i][j] = true;// 当前字符相等时,之前也相等,当前位置相等
					} else {// 尝试删除使之匹配
						dp[i][j] = false;
						int index = j - 2;// j-1是当前相等位置,找前一个位置的*,所以是j-2
						while (index > 0 && chars2[index] == '*') {// 连续的间隔*可以删除之前的字符
							if (dp[i - 1][index - 1]) {// 删除index位后,i-1,index-1位置相等,最后一位匹配找前一位
								dp[i][j] = true;// 那么i,j位置可以达到相等
								break;
							}
							index -= 2;
						}
					}
				} else if (chars2[j - 1] == '*') {// 当前字符不等,用*匹配
					if (dp[i][j - 1]) {// 当前字符不等,i,j-1位置相等,j位置的*当0用时,i,j位置相等.没用的*,
						dp[i][j] = true;
					} else if ((chars1[i - 1] == chars2[j - 2] || chars2[j - 2] == '.') && dp[i - 1][j]) {
// 条件1:
// chars1[i - 1] == chars2[j - 2] || chars2[j - 2] =='.',
// 是当前s第i个字符,同p的第j-1个字符相等,下标分别对应i-1和j-2
// 条件1:即s最后一个字符同p的前一个字符相匹配,p末尾*才能当复制用
// 条件2:dp[i - 1][j]:
// 在满足条件1的同时,满足条件2,当前i,j位置才能是true
// 不是满足dp[i - 1][j - 1]==true: 如 aaaaa 同 a.*
// *当复制使用,意味着s串在s-1长度,同p是匹配时,
// 即dp[i - 1][j]==true,对应截至chars1[i - 2],chars2[j - 1]匹配时,
// 由于p末尾*和条件1的原因,s末尾可以无限增加p-1位置字符,都会使得匹配成立
// abb 同 ab* 匹配,abb后可以无限增加b,abbb同ab*满足条件1和条件2
						dp[i][j] = true;
					} else {
						dp[i][j] = false;
						int index = j - 1;// j-1是当前相等位置,要找到最近和j-1相匹配的位置,所以从index=j-1开始
						while (index > 0 && chars2[index] == '*') {// 连续的间隔*可以删除之前的字符
							if (dp[i][index - 1]) {// 删除index位后,i,index-1位置相等的话,最后一位不匹配,找最后一位
								dp[i][j] = true;
								break;
							}
							index -= 2;
						}
					}

				}
			}
		}
//		H.printObject(chars1);
//		H.printObject(chars2);
//		H.printObject(dp);
		return dp[len1][len2];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.myBug1();
		so.myBug2();
		so.myBug3();
		so.myBug4();
		so.myBug5();
		so.myBug6();
		so.debug5();
		so.myBug7();
		so.myBug8();
		so.myBug9();
		so.myBug10();
	}

}
